package zw_301_400.zw_349_两个数组的交集;

import java.util.*;
import java.util.stream.Collectors;

class Solution {


    public static void main(String[] args) {
        int[] nums1 = {1, 2, 2, 1}, nums2 = {2, 2};
        int[] n = intersection(nums1, nums2);
        for (int i : n) {
            System.out.println(i);
        }
    }

    /**
     * 排序 + 双指针
     * 时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是两个数组的长度。
     * 对两个数组排序的时间复杂度分别是O(mlogm)和O(nlogn)，双指针寻找交集元素的时间复杂度是O(m+n)，因此总时间复杂度是O(mlogm+nlogn)。
     * 空间复杂度：O(logm+logn)，其中 m 和 n 分别是两个数组的长度。空间复杂度主要取决于排序使用的额外空间。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[length1 + length2];
        int index = 0, index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                // 保证加入元素的唯一性
                if (index == 0 || num1 != intersection[index - 1]) {
                    intersection[index++] = num1;
                }
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }


//    public static int[] intersection(int[] nums1, int[] nums2) {
//        Set<Integer> set = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
//        return Arrays.stream(nums2).distinct().filter(set::contains).toArray();
//    }

//    public static int[] intersection(int[] nums1, int[] nums2) {
//        Set<Integer> set1 = new HashSet<>(),set2 = new HashSet<>();
//        List<Integer> list = new ArrayList<>();
//        for(int i:nums1){
//            list.add(i);
//        }
//        for(int i:nums2){
//            set2.add(i);
//        }
//        list.retainAll(set2);
//        set1.addAll(list);
//        return set1.stream().mapToInt(i->i).toArray();
//    }


//    public static int[] intersection(int[] nums1, int[] nums2) {
//        HashSet<Integer> set1 = new HashSet<>();
//        HashSet<Integer> set2 = new HashSet<>();
//        int count = 0;
//        for (int i = 0; i < nums1.length; i++) {
//            set1.add(nums1[i]);
//        }
//        for (int i = 0; i < nums2.length; i++) {
//            set2.add(nums2[i]);
//        }
//        for (int item : set2) {
//            if (set1.contains(item)){
//                count++;
//            }
//        }
//        int[] ans = new int[count];
//        for (int item : set2) {
//            if (set1.contains(item)){
//                ans[--count] = item;
//            }
//        }
//        return ans;
//    }
}
